package leetcode.每日一题;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author :songyaozhang
 * @date :Created 2021/8/5 16:55
 * @description :
 */
public class 杨辉三角II {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.getRow(5));
    }

    //滚动数组
    /*
    class Solution {
        public List<Integer> getRow(int rowIndex) {
            List<Integer> pre = new ArrayList<>();
            pre.add(1);
            List<Integer> cur;
            for (int i = 0; i <= rowIndex; i++) {
                cur = new ArrayList<>();
                for (int j = 0; j <= i; j++) {
                    if (j == 0 || j == i) {
                        cur.add(1);
                    } else
                        cur.add(pre.get(j - 1) + pre.get(j));
                }
                pre = cur;
                System.out.println(cur);
            }
            return pre;
        }
    }
     */

    //只使用一个数组
    class Solution {
        public List<Integer> getRow(int rowIndex) {
            List<Integer> row = new ArrayList<>();
            row.add(1);
            for (int i = 1; i <= rowIndex; ++i) {
                row.add(0);
                for (int j = i; j > 0; --j) {
                    row.set(j, row.get(j) + row.get(j - 1));
                }
            }
            return row;
        }
    }

}
